package org.test.analysis.sort;

import junit.framework.Assert;

import org.junit.Test;

/**
 * 合并排序
 * 
 * @author game
 * 
 */
public class Mergesort {

	/**
	 * 把c数组用合并排序弄成有序的。
	 * @param c
	 */
	public void mergesort(char c[]){
		if(c.length>1){//为1个元素
			char[] a = new char[c.length/2];//向下取整
			char[] b = new char[(int) Math.ceil((double)(c.length)/2)];//向上取整
			
			Sutil.copycharArray(0, c.length/2-1, c, a);
			Sutil.copycharArray(c.length/2, c.length-1, c, b);
			mergesort(a);
			mergesort(b);
			merge(a, b, c);
		}
	}
	
	
	@Test
	public void testmergesort(){
		char[] r = { 'z', 'c', 'f','e','w','y','g','d','k','k'};
		mergesort(r);
		System.out.println(r);
	}

	
	
	/**
	 * 
	 * 把a和b中的升序数组合并成c
	 * 
	 * @param a
	 * @param b
	 * @param c
	 */
	public void merge(char a[], char b[], char c[]) {
		int i, j, k;
		for (i = 0, j = 0, k = 0; (i < a.length) || (j < b.length);) {
			if (i >= a.length) { // a到了尽头，剩下的b包办了
				c[k++] = b[j++];
			} else if (j >= b.length) { // b到了尽头，剩下的a包办了
				c[k++] = a[i++];
			} else if (a[i] < b[j]) {// a大,放入c
				c[k++] = a[i++];
			} else { // b大,放入c
				c[k++] = b[j++];
			}
		}
	}

	@Test
	public void testmerge() {
		char[] a = { 'a', 'c', 'f' };
		char[] b = { 'b', 'd', 'e' };
		char[] c = new char[a.length + b.length];
		merge(a, b, c);
		System.out.println(a);
		System.out.println(b);
		System.out.println(c);
		

	}
}
